Congestion avoidance techniques are essential to the operation of networks and network devices. One such technique known in the art as “Random Early Discard” or “RED” is described in a publication by S. Floyd and V. Jacobson entitled “Random Early Detection Gateways for Congestion Avoidance,” (Transactions on Networking, August 1993), which is hereby incorporated by reference for all purposes.
The basic principle behind RED is to control the average length of a network device's (e.g., a router's) output queue in order to avoid long term congestion. To achieve this goal, RED must work tightly coupled with transport protocols, such as TCP, which are equipped with their own congestion avoidance mechanisms and are thus capable to react to congestion indications generated by RED routers.
FIG. 1 includes graph 100 that illustrates how RED works. For each incoming packet, the average queue length is calculated. (Please note that the terms “packet” and “frame” may be used interchangeably herein.) If the average queue length is below a predefined minimum threshold 105, the packet is accepted and stored in the output queue for transmission. If the average queue size is above the minimum threshold 105 but below a predefined maximum threshold 110, a packet marking probability is computed and the packet gets marked according to this probability. The marking probability is proportional to the average queue size. Therefore, when the queue is larger, there is a higher probability for an incoming packet to get marked. Finally, if the average queue size is above the maximum threshold 110, all incoming packets are marked until the average queue size falls again below the maximum threshold 110.
It is responsibility of the transport protocol to take the appropriate countermeasures when it detects packets marked by RED. When TCP is being used in the absence of an explicit method of marking packets, packets can only be “marked” by discarding them, with TCP interpreting the loss of packets as a congestion indication. When packet drops are detected, TCP sources immediately reduce their transmission rate, causing a reduction of the traffic volume at the congested router(s). Discarding packets is also a useful means to control average queue size when non-reactive transport protocols such as UDP are exploited. The RED algorithm has been implemented in some output-buffered network devices, including the Catalyst 6500 switch and the 7200 series router provided by Cisco Systems, Inc., to prevent congestion of output buffers.
It would seem to be desirable to deploy an active queue management (“AQM”) technique such as RED in input-buffered switches to keep congestion of input buffers and Virtual Output Queues (“VOQs”) under control. However, the RED algorithm presents scalability issues and other challenges. In an output-buffered network device having N ports, at least N instances of the RED algorithm need to be applied. It may not be feasible to have a dedicated instance of the RED mechanism associated with each VOQ of an input-buffered network device. In such a device, there could be thousands of VOQs mapped on a physical buffer. Because each input buffer implements a VOQ for each output of the system, N2 instances of the RED algorithm would need to be deployed for an input-buffered switch having N ports. It would be both difficult and expensive to provide an average queue length estimator to each VOQ.
If one were to apply a traditional RED algorithm on an entire buffer shared by many VOQs, flows that are not contributing to congestion could be adversely affected. On the other hand, if a traditional RED method were applied on a per-VOQ basis for potentially thousands of VOQS, each queue could be too small to obtain a meaningful average occupancy value, particularly if the buffer is small with respect to the number of VOQS.
Considering the foregoing, a traditional RED method would not seem to be a desirable way to implement AQM for input-buffered switches. It would be desirable to implement methods and devices that overcome at least some of the aforementioned shortcomings of the prior art.